from tools_algorithm import *


class Solution:
    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:

        m, n = len(grid), len(grid[0])

        @cache
        def f(i, j, md):
            if i == m or j == n:
                return 0
            if i == m - 1 and j == n - 1:
                return int((grid[i][j] + md) % k == 0)
            md = (grid[i][j] + md) % k
            return (f(i + 1, j, md) + f(i, j + 1, md)) % 1000000007

        return f(0, 0, 0)


s = Solution()
print(s.numberOfPaths(grid=[[7, 3, 4, 9], [2, 3, 6, 2], [2, 3, 7, 0]], k=1))

fl = test_file_path(__file__, 2)
c = []
n = 100
for _ in range(n):
    t = []
    for _ in range(n + 2):
        t.append(random.randint(1, 100))
    c.append(t)
print(c, file=fl)
